home *** CD-ROM | disk | FTP | other *** search
/ Aminet 40 / Aminet 40 (2000)(Schatztruhe)[!][Dec 2000].iso / Aminet / dev / lang / Python16_Src.lha / Python16_Source / Parser / firstsets.c < prev    next >
Encoding:
C/C++ Source or Header  |  2000-08-03  |  2.1 KB  |  112 lines
  1. /* Computation of FIRST stets */
  2.  
  3. #include "pgenheaders.h"
  4. #include "grammar.h"
  5. #include "token.h"
  6.  
  7. extern int Py_DebugFlag;
  8.  
  9. /* Forward */
  10. static void calcfirstset Py_PROTO((grammar *, dfa *));
  11.  
  12. void
  13. addfirstsets(g)
  14.     grammar *g;
  15. {
  16.     int i;
  17.     dfa *d;
  18.     
  19.     printf("Adding FIRST sets ...\n");
  20.     for (i = 0; i < g->g_ndfas; i++) {
  21.         d = &g->g_dfa[i];
  22.         if (d->d_first == NULL)
  23.             calcfirstset(g, d);
  24.     }
  25. }
  26.  
  27. static void
  28. calcfirstset(g, d)
  29.     grammar *g;
  30.     dfa *d;
  31. {
  32.     int i, j;
  33.     state *s;
  34.     arc *a;
  35.     int nsyms;
  36.     int *sym;
  37.     int nbits;
  38.     static bitset dummy;
  39.     bitset result;
  40.     int type;
  41.     dfa *d1;
  42.     label *l0;
  43.     
  44.     if (Py_DebugFlag)
  45.         printf("Calculate FIRST set for '%s'\n", d->d_name);
  46.     
  47.     if (dummy == NULL)
  48.         dummy = newbitset(1);
  49.     if (d->d_first == dummy) {
  50.         fprintf(stderr, "Left-recursion for '%s'\n", d->d_name);
  51.         return;
  52.     }
  53.     if (d->d_first != NULL) {
  54.         fprintf(stderr, "Re-calculating FIRST set for '%s' ???\n",
  55.             d->d_name);
  56.     }
  57.     d->d_first = dummy;
  58.     
  59.     l0 = g->g_ll.ll_label;
  60.     nbits = g->g_ll.ll_nlabels;
  61.     result = newbitset(nbits);
  62.     
  63.     sym = PyMem_NEW(int, 1);
  64.     if (sym == NULL)
  65.         Py_FatalError("no mem for new sym in calcfirstset");
  66.     nsyms = 1;
  67.     sym[0] = findlabel(&g->g_ll, d->d_type, (char *)NULL);
  68.     
  69.     s = &d->d_state[d->d_initial];
  70.     for (i = 0; i < s->s_narcs; i++) {
  71.         a = &s->s_arc[i];
  72.         for (j = 0; j < nsyms; j++) {
  73.             if (sym[j] == a->a_lbl)
  74.                 break;
  75.         }
  76.         if (j >= nsyms) { /* New label */
  77.             PyMem_RESIZE(sym, int, nsyms + 1);
  78.             if (sym == NULL)
  79.                 Py_FatalError(
  80.                     "no mem to resize sym in calcfirstset");
  81.             sym[nsyms++] = a->a_lbl;
  82.             type = l0[a->a_lbl].lb_type;
  83.             if (ISNONTERMINAL(type)) {
  84.                 d1 = PyGrammar_FindDFA(g, type);
  85.                 if (d1->d_first == dummy) {
  86.                     fprintf(stderr,
  87.                         "Left-recursion below '%s'\n",
  88.                         d->d_name);
  89.                 }
  90.                 else {
  91.                     if (d1->d_first == NULL)
  92.                         calcfirstset(g, d1);
  93.                     mergebitset(result,
  94.                             d1->d_first, nbits);
  95.                 }
  96.             }
  97.             else if (ISTERMINAL(type)) {
  98.                 addbit(result, a->a_lbl);
  99.             }
  100.         }
  101.     }
  102.     d->d_first = result;
  103.     if (Py_DebugFlag) {
  104.         printf("FIRST set for '%s': {", d->d_name);
  105.         for (i = 0; i < nbits; i++) {
  106.             if (testbit(result, i))
  107.                 printf(" %s", PyGrammar_LabelRepr(&l0[i]));
  108.         }
  109.         printf(" }\n");
  110.     }
  111. }
  112.